package day5;

public class 孩子们的游戏 {
	//dp[i]: i个孩子围成一圈，最后胜出孩子的编号
	public int LastRemaining_Solution2 (int n, int m) {
        // write code here
        int[] dp=new int[n+1];
        dp[1]=0;
        for(int i=2;i<=n;i++) {
        	dp[i]=(dp[i-1]+m)%i;
        }
        return dp[n];
    }
	
	
	//模拟：一直循环所有孩子，逢m删掉一个，直到只剩下一个
	//     1.数组模拟   2.循环链表模拟
	public int LastRemaining_Solution1 (int n, int m) {
        // write code here
        int[] arr=new int[n];
        boolean[] flag=new boolean[n];
        int count=0,pos=-1,ret=0;
        while(n-ret>1){
            pos=(pos+1)%n;
            if(flag[pos]==true){
                continue;
            }
            count++;
            if(count%m==0){
                flag[pos]=true;
                ret++;
            }
        }
        for(int i=0;i<n;i++){
            if(flag[i]==false){
                return i;
            }
        }
        return 0;
    }
}
